// const weight = [1, 2, 3, 5];

// const value = [15, 24, 23, 60];

// function maxbag(total) {
//   //   let dp = []
//   let dp = new Array(weight.length)
//     .fill(0)
//     .map((item) => new Array(total + 1).fill(0));

//   dp[0].forEach((e, i) => {
//     if (i >= weight[0]) dp[0][i] = value[0];
//   });

//   for (let i = 1; i < weight.length; i++) {
//     for (j = 0; j <= total; j++) {
//       if (j - weight[i] < 0) {
//         dp[i][j] = dp[i - 1][j];
//       } else {
//         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
//       }
//     }
//   }

//   console.table(dp);

//   return dp[weight.length - 1][size];
// }

// maxbag(9);

// function maxbag2() {
//   dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
// }

// function testWeightBagProblem(weight, value, size) {
//   // 定义 dp 数组
//   const len = weight.length,
//     dp = Array(len)
//       .fill()
//       .map(() => Array(size + 1).fill(0));

//   // 初始化
//   for (let j = weight[0]; j <= size; j++) {
//     dp[0][j] = value[0];
//   }

//   console.log("🚀 ～ file: bag.js:38 ～ testWeightBagProblem ～ dp:", dp);

//   // weight 数组的长度len 就是物品个数
//   for (let i = 1; i < len; i++) {
//     // 遍历物品
//     for (let j = 0; j <= size; j++) {
//       // 遍历背包容量
//       if (j < weight[i]) dp[i][j] = dp[i - 1][j];
//       else
//         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
//     }
//   }

//   console.table(dp);

//   return dp[len - 1][size];
// }

// function test() {
//   console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
// }

// test();

function testWeightBagProblem(wight, value, size) {
  const len = wight.length,
    dp = Array(size + 1).fill(0);

  //为什么要倒叙 保证每个物品被添加1 次
  for (let i = 1; i <= len; i++) {
    for (let j = size; j >= wight[i - 1]; j--) {
      dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
    }
  }
  console.table(dp);

  return dp[size];
}

function test() {
  console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();
